//整数数组 sockets 记录了一个袜子礼盒的颜色分布情况，其中 sockets[i] 表示该袜子的颜色编号。礼盒中除了一款撞色搭配的袜子，每种颜色的袜子均
//有两只。请设计一个程序，在时间复杂度 O(n)，空间复杂度O(1) 内找到这双撞色搭配袜子的两个颜色编号。 
//
// 
//
// 示例 1： 
//
// 
//输入：sockets = [4, 5, 2, 4, 6, 6]
//输出：[2,5] 或 [5,2]
// 
//
// 示例 2： 
//
// 
//输入：sockets = [1, 2, 4, 1, 4, 3, 12, 3]
//输出：[2,12] 或 [12,2] 
//
// 
//
// 提示： 
//
// 
// 2 <= sockets.length <= 10000 
// 
//
// Related Topics 位运算 数组 👍 890 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-05-18 13:34:29
 * @description LCR 177.撞色搭配
 */
public class ShuZuZhongShuZiChuXianDeCiShuLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 ShuZuZhongShuZiChuXianDeCiShuLcof fun=new ShuZuZhongShuZiChuXianDeCiShuLcof();
	 	 Solution solution = fun.new Solution();
		 System.out.println(5^3);//101  11
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 // 有两个数字a b出现了一次，其余都出现了两次
	//与或得到的是 a^b
	//选取a^b的任意一个为1的位置，这个位置代表a和b在这个为的二进制不一样
	//根据这个位置把数组分成两组，则a和b会在不同的组中
	//其他数字因为都是出现两次，所以两次都会被分到一个组中
	//最后异或每个组的所有数字，剩下的就是a,b
    public int[] sockCollocation(int[] sockets) {
		int res=0;
		for (int socket : sockets) {
			res^=socket;
		}
		int m=1;
		while ((m&res)==0){
			m<<=1; //找到为1 的这一位
		}
		int a=0,b=0;
		for (int socket : sockets) {
			if((socket&m)!=0){
				a^=socket;
			}else {
				b^=socket;
			}
		}
		return new int[]{a,b};
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
